import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * Date: 2025-02-12
 * Time: 14:34
 */

class ImpLess implements Comparator<Integer>{

    @Override
    public int compare(Integer o1, Integer o2) {
        return o1.compareTo(o2);
    }
}
class ImpBig implements Comparator<Integer>{

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}

public class Test {
    public static int[] topK(int[] array,int k){
        int[] ret = new int[k];
        if (k <= 0){
            return ret;
        }

        PriorityQueue<Integer> queue = new PriorityQueue<>(new ImpBig());
        //O(k*logK){
        for (int i = 0; i < k; i++) {
            queue.offer(array[i]);
        }
        //从第k+1个元素开始进行遍历O（n-k）
        for (int i = k; i < array.length; i++) {
            //先获取堆顶元素
            int val = queue.peek();
            if (val > array[i]){
                queue.poll();
                queue.offer(array[i]);
            }
        }
        //走到这里队列里面就是前k个最小的元素
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll();
        }
        return ret;
    }
    public static int[] topk1(int[] array,int k){
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        for (int i = 0; i < array.length; i++) {
            queue.offer(array[i]);
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll();
        }
        return ret;
    }
    public static void main(String[] args) {
        int[] array = {1,12,3,41,5,16,7,81,9,10};
        int[] ret = topK(array,3);
        System.out.println(Arrays.toString(ret));
    }
    public static void main3(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new ImpBig());
        queue.offer(10);
        queue.offer(5);

        System.out.println(queue.peek());
    }

    public static void main2(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.offer(10);
        queue.offer(2);
        queue.offer(5);

        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
    }
    public static void main1(String[] args) {
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        TestHeap testHeap = new TestHeap();
        testHeap.init(array);
    }
}
